package leetcode.code2573;

import java.util.Arrays;

public class Solution {
	public String findTheString(int[][] lcp) {
		int n = lcp.length;
		char[] ans = new char[n];
		Arrays.fill(ans, '0');
		for (int i = 0, s = 0; i < 26 && s < n; i++, s++) {
			char c = (char) ('a' + i);
			while (s < n && ans[s] != '0') {
				s++;
			}
			for (int j = s; s < n && j < n; j++) {
				if (lcp[s][j] != 0) {
					ans[j] = c;
				}
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j >= 0; j--) {
				char a = ans[i], b = ans[j];
				if (a == '0' || b == '0')
					return "";
				if (a == b) {
					if (i == n - 1 || j == n - 1) {
						if (lcp[i][j] != 1) {
							return "";
						}
					} else if (lcp[i][j] - 1 != lcp[i + 1][j + 1]) {
						return "";
					}
				} else {
					if (lcp[i][j] != 0) {
						return "";
					}
				}
			}
		}
		return new String(ans);
	}
}
